package model;
@SuppressWarnings("unchecked")
public class QuickSort extends Sorter {

	public QuickSort() {
		super();
		statistics = new Statistics();
	}

	public void sort(Comparable[] workArray) {
	    long beforeTime = System.nanoTime();
	    
		QSort(workArray, 0, workArray.length - 1);
		
	    long afterTime = System.nanoTime();
	    
	    statistics.setRunTime(afterTime - beforeTime);
	}

	private void QSort(Comparable[] workArray, int l, int u) { 

		if (u <= l) {
			return;
		} else {
			
			int i = l, j = u;
			while (i != j) {
				
				while (workArray[j].compareTo(workArray[i]) > 0 ) {
					j--;
					statistics.incrementChecks();
				}
				Integer tmp;
				if (i != j) {
					// --------------------
				    	//Swap
				    	statistics.incrementSwaps();
				    	
					tmp = (Integer) workArray[i];
					workArray[i] = workArray[j];
					workArray[j] = tmp;
//					System.out.println("SWAP  i = " + i + " j = " + j);
//					for(int g=0;g<workArray.length;g++){
//						System.out.println(g+" -> "+workArray[g]);
//					}
					
					if(simulation)
					PushSwapToQueue(i, j);
					// --------------------
					tmp = j;
					j = i + 1;
					i = tmp;
					// --------------------
				}
				if (i > j) {
					while (workArray[j].compareTo( (Integer) workArray[i])<0) {
						j++;
						statistics.incrementChecks();
					}
					if (i != j) {
						// --------------------
					    	//Swap
					    	statistics.incrementSwaps();
					    	
						tmp = (Integer) workArray[i];
						workArray[i] = workArray[j];
						workArray[j] = tmp;
//						System.out.println("SWAP  i = " + i + " j = " + j);
//						for(int g=0;g<workArray.length;g++){
//							System.out.println(g+" -> "+workArray[g]);
//						}
						
						if(simulation)
						PushSwapToQueue(j, i);
						// --------------------
						tmp = j;
						j = i - 1;
						i = tmp;
						// --------------------
					}
				}
			}
			QSort(workArray, l, i - 1);
			QSort(workArray, i + 1, u);
		}
	}

	@Override
	public int getComplexity(int arraySize) {
	    return (int) (Math.pow(arraySize, 2)*.5);
	}

}
